package 二分法;

import org.junit.Test;

public class search33 {
    /**
     * 这也是一个变形的二分法
     * 利用的暴力的算法是的遍历
     * <p>
     * 通过的判断 左边断电和右端点的来比较 阶段是有序的 可以通过判断的来实现
     *
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        int n = nums.length;
        // 当没有数据的时候
        if (n == 0) {
            return -1;
        }
        // 当只有一个数据的时候
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int l = 0, r = n - 1;
        // 二分法
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (nums[mid] == target) {
                return mid;
            }
            // 判断左边和中间的值
            if (nums[0] <= nums[mid]) {
                // 表示的是有序的
                if (nums[0] <= target && target < nums[mid]) {
                    // 判断值时候在左边的数组里面就可以进行缩减
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                // 右边是有序的
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }

    @Test
    public void test() {
        int search = search(new int[]{4, 5, 6, 7, 0, 1, 2}, 5);
        System.out.println(search);
    }
}
